package meituan;

import org.junit.Test;

/**
 * @Description 动态规划:线性DP
 * 【题目】给定不同面额的硬币 coins 和一个总金额 amount，需要你编写一个函数计算可以凑成总金额所需的最少的硬币个数。
 * 如果没有任何一种硬币组合能组成总金额，则返回 -1。你可以认为每种硬币的数量是无限的。
 * @Author luozhenting
 * @Date 2021/10/14
 **/
public class CoinChange {
    public int coinChange(int[] coins, int amount) {
        // 没有解的时候，设置一个较大的值
        final int INF = Integer.MAX_VALUE / 4;
        int[] dp = new int[amount + 1];
        // 一开始给所有的数设置为不可解。
        for (int i = 1; i <= amount; i++) {
            dp[i] = INF;
        }
        // DP的初始条件
        dp[0] = 0;
        for (int i = 0; i < amount; i++) {
            for (int y : coins) {
                // 注意边界的处理，不要越界
                if (y <= amount && i + y < amount + 1 && i + y >= 0) {
                    // 正向推导时的递推公式!
                    dp[i + y] = Math.min(dp[i + y], dp[i] + 1);
                }
            }
        }
        return dp[amount] >= INF ? -1 : dp[amount];
    }

    @Test
    public void myTest() {
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println(this.coinChange(coins, amount));
    }
}
